//字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> 
//s2 -> ... -> sk： 
//
// 
// 每一对相邻的单词只差一个字母。 
// 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。 
// sk == endWord 
// 
//
// 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 
//中的 单词数目 。如果不存在这样的转换序列，返回 0 。 
// 
//
// 示例 1： 
//
// 
//输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot",
//"log","cog"]
//输出：5
//解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
// 
//
// 示例 2： 
//
// 
//输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot",
//"log"]
//输出：0
//解释：endWord "cog" 不在字典中，所以无法进行转换。 
//
// 
//
// 提示： 
//
// 
// 1 <= beginWord.length <= 10 
// endWord.length == beginWord.length 
// 1 <= wordList.length <= 5000 
// wordList[i].length == beginWord.length 
// beginWord、endWord 和 wordList[i] 由小写英文字母组成 
// beginWord != endWord 
// wordList 中的所有字符串 互不相同 
// 
// Related Topics广度优先搜索 | 哈希表 | 字符串 
//
// 👍 1139, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.*;

class WordLadder {
    public static void main(String[] args) {
        Solution solution = new WordLadder().new Solution();
        List<String> list = new ArrayList<>();
        list.addAll(Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
        solution.ladderLength("hit", "cog", list);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 和433基本一致
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if (beginWord.equals(endWord)) return 0;
            Set<String> wordSet = new HashSet<>();
            Set<String> visited = new HashSet<>();
            for (String s : wordList) wordSet.add(s);

            if (!wordSet.contains(endWord)) return 0;

            Queue<String> queue = new LinkedList<>();
            queue.offer(beginWord);

            int step = 1;
            while (!queue.isEmpty()) {
                int size = queue.size();
                step++;
                for (int i = 0; i < size; i++) {
                    String cur = queue.poll();
                    for (int j = 0; j < cur.length(); j++) {
                        for (int k = 0; k <= 26; k++) {
                            char c = (char) (k + 'a');
                            if (c != cur.charAt(j)) {
                                StringBuilder sb = new StringBuilder(cur);
                                sb.setCharAt(j, c);
                                String next = sb.toString();

                                if (!visited.contains(next) && wordSet.contains(next)) {
                                    if (next.equals(endWord)) return step;
                                    visited.add(next);
                                    queue.offer(next);
                                }
                            }
                        }
                    }
                }
            }

            return 0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
